#include <vector>
using std::vector;

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
{
    int n = inorder.size();
    if (n == 0)
    {
        return nullptr;
    }

    TreeNode* root = new TreeNode(postorder[n - 1]);

    int i = 0;
    // 
    while (inorder[i] != postorder[n - 1])
    {
        ++i;
    }

    vector<int> left_i(inorder.begin(), inorder.begin() + i);
    vector<int> left_p(postorder.begin() + 1, postorder.begin() + 1 + i);
    vector<int> right_i(inorder.begin() + i + 1, inorder.end());
    vector<int> right_p(postorder.begin() + i + 1, postorder.end());

    root->left = buildTree(left_i, left_p);
    root->right = buildTree(right_i, right_p);

    return root;
}

int main()
{
    vector<int> v1 = { 9,3,15,20,7 };
    vector<int> v2 = { 9,15,7,20,3 };
    buildTree(v1, v2);

    return 0;
}
